package com.javabasic.algorithm.leetcode;

/**
 * @author mir.xiong
 * @version 1.0
 * @description
 * @see
 * @since Created by work on 2024/3/31 21:38
 */
public class VerifyPreorderSerializationofABinaryTree {

    /**
     * 记录反推二叉树过程中的数组尾下标。
     */
    int tail = 0;

    /**
     * 模拟算法：
     * 根据按照题目描述所说二叉树的前序遍历的规则，以及对应的序列；反推二叉树；在反推的过程中验证所给的二叉树序列是否正确。
     * @param preorder
     * @return
     */
    public boolean isValidSerialization(String preorder) {
        int len = preorder.length();
        String[] tree = preorder.split(",");
        tail = 0;
        return traversalTree(0,  tree) && tail == tree.length - 1;
    }

    private boolean traversalTree(int index, String[] tree) {
        if (index >= tree.length) {
            return false;
        }
        if ("#".equals(tree[index])) {
            return true;
        }
        int tailIndex = tail;
        tail += 2;
        /**
         * 注意，这个不能直接用二叉树的特性 2*index+1、2*index+2 因为二叉树并不是满二叉树或者完全二叉树，且遍历是按序号追加的不具备这个性质
         */
        boolean left = traversalTree(tailIndex + 1, tree);
        boolean right = traversalTree(tailIndex + 2, tree);

        if (!left || !right) {
            return false;
        }
        return true;
    }

}
